package com.walter.learn.Sort;

import org.junit.Test;

/**
 * @ProjectName: learnOwner
 * @Package: com.walter.learn.Sort
 * @ClassName: SortLearn
 * @Description: 十大排序
 * @Author: 唐朝
 * @CreateDate: 2019/2/20 16:47
 * @UpdateUser: 更新者
 * @UpdateDate: 2019/2/20 16:47
 * @UpdateRemark: 更新说明
 * @Version: 1.0
 */

public class SortLearn {


    @Test
    public void main() {
        int[] array = {0, 6, 4, 8, 2};
//        bubbleSort(array);
//        insertSort(array);
//        sheelSort(array);
        selectSort(array);
        getAfterSortResult(array);

    }

    //得到排序之后的结果
    public void getAfterSortResult(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    /**
     * 冒泡排序 两两比较大的放在后面
     *
     * @param array
     */
    public void bubbleSort(int[] array) {
//        int[] a ={0,6,4,8,2};

        int len = array.length;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len - i - 1; j++) {//注意第二重循环的条件
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 直接插入排序（适用于在已经排好序的数据中插入数据）----从后往前插
     * 首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。
     * 设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。
     * 从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。
     * 将当前数放置到空着的位置，即j+1。
     *
     * @param array 要排序的数组
     */
    public void insertSort(int[] array) {
        int len = array.length;//单独把数组长度拿出来，提高效率
        int insertNum;//要插入的数
        for (int i = 1; i < len; i++) {//因为第一次不用，所以从1开始
            insertNum = array[i];
            int j = i - 1;//序列元素个数
            while (j >= 0 && array[j] > insertNum) {//从后往前循环，将大于insertNum的数向后移动
                array[j + 1] = array[j];//元素向后移动
                j--;
            }
            array[j + 1] = insertNum;//找到位置，插入当前元素
        }
    }

    /**
     * 希尔排序----直接插入排序的升级版
     *
     * @param array
     */
    public void sheelSort(int[] array) {
        int len = array.length;//单独把数组长度拿出来，提高效率
        while (len != 0) {
            len = len / 2;
            for (int i = 0; i < len; i++) {//分组
                for (int j = i + len; j < array.length; j += len) {//元素从第二个开始
                    int k = j - len;//k为有序序列最后一位的位数
                    int temp = array[j];//要插入的元素
                    while (k >= 0 && temp < array[k]) {//从后往前遍历
                        array[k + len] = array[k];
                        k -= len;//向后移动len位
                    }
                    array[k + len] = temp;
                }
            }
        }
    }

    /**
     * 简单选择排序
     *
     * @param array
     */
    public void selectSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {//循环次数
            int value = array[i];
            int position = i;
            for (int j = i + 1; j < len; j++) {//找到最小的值和位置
                if (array[j] < value) {
                    value = array[j];
                    position = j;
                }
            }
            array[position] = array[i];//进行交换
            array[i] = value;
        }
    }

}
